export class RangeHeap {
  private x1: number[] = []
  private y1: number[] = []
  private x2: number[] = []
  private y2: number[] = []
  private count: number = 0
  addPoint(x: number, y: number) {
    const i1 = Math.floor(this.count / 10) << 1
    const i2 = Math.floor(this.count / 100) << 1

    if (this.count % 10 === 0) {
      this.x1.push(x, x)
      this.y1.push(y, y)
    }
    if (this.count % 100 === 0) {
      this.x2.push(x, x)
      this.y2.push(y, y)
    }

    this.x1[i1] = Math.min(this.x1[i1], x)
    this.y1[i1] = Math.min(this.y1[i1], y)
    this.x2[i2] = Math.min(this.x2[i2], x)
    this.y2[i2] = Math.min(this.y2[i2], y)
    this.x1[i1 + 1] = Math.max(this.x1[i1 + 1], x)
    this.y1[i1 + 1] = Math.max(this.y1[i1 + 1], y)
    this.x2[i2 + 1] = Math.max(this.x2[i2 + 1], x)
    this.y2[i2 + 1] = Math.max(this.y2[i2 + 1], y)

    this.count += 1
  }

  interact(bounds: number[]): number[] | null {
    const [x1, y1, x2, y2] = bounds
    let i2 = 0
    let i1 = 0
    const l2 = this.x2.length
    const l1 = this.x1.length
    if (this.count < 10) {
      const x21 = this.x2[i2]
      const x22 = this.x2[i2 + 1]
      const y21 = this.y2[i2]
      const y22 = this.y2[i2 + 1]
      const crossX2 = !((x21 < x1 && x22 < x1) || (x21 > x2 && x22 > x2))
      const crossY2 = !((y21 < y1 && y22 < y1) || (y21 > y2 && y22 > y2))
      if (crossX2 && crossY2) {
        return [0]
      }
      return null
    }
    let result: number[] | null = null
    for (; i2 < l2; i2 += 2) {
      const x21 = this.x2[i2]
      const x22 = this.x2[i2 + 1]
      const y21 = this.y2[i2]
      const y22 = this.y2[i2 + 1]
      const crossX2 = !((x21 < x1 && x22 < x1) || (x21 > x2 && x22 > x2))
      const crossY2 = !((y21 < y1 && y22 < y1) || (y21 > y2 && y22 > y2))
      if (crossX2 && crossY2) {
        for (i1 = i2 * 10; i1 < l1; i1 += 2) {
          const x11 = this.x1[i1]
          const x12 = this.x1[i1 + 1]
          const y11 = this.y1[i1]
          const y12 = this.y1[i1 + 1]
          const crossX1 = !((x11 < x1 && x12 < x1) || (x11 > x2 && x12 > x2))
          const crossY1 = !((y11 < y1 && y12 < y1) || (y11 > y2 && y12 > y2))
          if (crossX1 && crossY1) {
            if (result === null) {
              result = [i1 >> 1]
            } else {
              result.push(i1 >> 1)
            }
          }
        }
      }
    }
    return result
  }
}
